/**
 * 1155. 掷骰子等于目标和的方法数
 */
public class No1155 {
    private final int MOD = (int) (1e9 + 7);
    private int k;
    private int[][] cache;

    /**
     * 1. 递归
     */
    public int numRollsToTarget1(int n, int k, int target) {
        this.k = k;
        cache = new int[n + 1][target + 1];
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < target + 1; j++) {
                cache[i][j] = -1;
            }
        }
        return dfs(n, target);
    }

    private int dfs(int i, int c) {
        if (c < i) return 0;
        else if (cache[i][c] != -1) return cache[i][c];
        else if (i == 0) {
            return cache[i][c] = c == 0 ? 1 : 0;
        } else {
            long curSum = 0;
            for (int j = 1; j <= k; j++) {
                curSum += dfs(i - 1, c - j) % MOD;
            }
            return cache[i][c] = (int) (curSum % MOD);
        }
    }

    /**
     * 2. 迭代
     */
    public int numRollsToTarget2(int n, int k, int target) {
        int[][] f = new int[n + 2][target + 1];
        for (int i = 0; i < n + 1; i++) {
            for (int c = 0; c < target + 1; c++) {
                if (c < i) f[i + 1][c] = 0;
                else if (i == 0) {
                    f[i + 1][c] = c == 0 ? 1 : 0;
                } else {
                    long curSum = 0;
                    for (int j = 1; c >= j && j <= k; j++) {
                        curSum += f[i][c - j] % MOD;
                    }
                    f[i + 1][c] = (int) (curSum % MOD);
                }
            }
        }
        return f[n + 1][target];
    }
}
